package leetcode.weekly.week304;

//Solution3Test
public class Solution3 {

	public int closestMeetingNode(int[] edges, int node1, int node2) {
		int n = edges.length;
		Integer[] been1 = new Integer[n];
		int cur = node1;
		int cnt = 0;
		while (cur != -1 && been1[cur] == null) {
			been1[cur] = cnt++;
			cur = edges[cur];
		}
		Integer[] been2 = new Integer[n];
		cur = node2;
		cnt = 0;
		while (cur != -1 && been2[cur] == null) {
			been2[cur] = cnt++;
			cur = edges[cur];
		}
		int ans = -1;
		cnt = Integer.MAX_VALUE;
		for (int i = 0; i < n; i++) {
			if (been1[i] != null && been2[i] != null) {
				int take = Math.max(been1[i], been2[i]);
				if (take < cnt) {
					cnt = take;
					ans = i;
				}
			}
		}
		return ans;
	}

}
